import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User:DELL
 * Date:2024-11-05
 * Time:14:51
 */
public class BinaryTree {
    static class TreeNode{
        char val;
        private TreeNode left;
        private TreeNode right;

        public TreeNode(char val) {
            this.val = val;
        }
    }
    //public TreeNode root;//将来这个引用指向的就是根节点
    public TreeNode createTree(){
        TreeNode A=new TreeNode('A');
        TreeNode B=new TreeNode('B');
        TreeNode C=new TreeNode('C');
        TreeNode D=new TreeNode('D');
        TreeNode E=new TreeNode('E');
        TreeNode F=new TreeNode('F');
        TreeNode G=new TreeNode('G');
        TreeNode H=new TreeNode('H');

        A.left=B;
        A.right=C;
        B.left=D;
        B.right=E;
        C.left=F;
        C.right=G;
        E.right=H;
        return A;
    }
    //前序遍历
    public void preOrder(TreeNode root) {
        if(root==null){
            return;
        }
        System.out.print(root.val+" ");
        preOrder(root.left);
        preOrder(root.right);
    }
    //将前序结果的遍历存储到List当中
    public List<TreeNode> preOrder2(TreeNode root) {
        List<TreeNode> ret=new ArrayList<>();
        if(root==null){
            return ret;
        }
        ret.add(root);
        List<TreeNode> leftTree=preOrder2(root.left);
        ret.addAll(leftTree);
        List<TreeNode> rightTree=preOrder2(root.right);
        ret.addAll(rightTree);
        return ret;
    }
    //中序遍历
    public void inOrder(TreeNode root){
        if(root==null){
            return;
        }
        inOrder(root.left);
        System.out.print(root.val+" ");
        inOrder(root.right);
    }
    //将中序结果的遍历存储到List当中
    public List<TreeNode> inOrder2(TreeNode root) {
        List<TreeNode> ret=new ArrayList<>();
        if(root==null){
            return ret;
        }
        List<TreeNode> leftTree=inOrder2(root.left);
        ret.addAll(leftTree);
        ret.add(root);
        List<TreeNode> rightTree=inOrder2(root.right);
        ret.addAll(rightTree);
        return ret;
    }
    //后序遍历
    public void postOrder(TreeNode root) {
        if(root==null){
            return;
        }
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val+" ");
    }

    //将后序结果的遍历存储到List当中
    public List<TreeNode> postOrder2(TreeNode root) {
        List<TreeNode> ret=new ArrayList<>();
        if(root==null){
            return ret;
        }
        List<TreeNode> leftTree=postOrder2(root.left);
        ret.addAll(leftTree);
        List<TreeNode> rightTree=postOrder2(root.right);
        ret.addAll(rightTree);
        ret.add(root);
        return ret;
    }

    // 获取树中节点的个数
    public int size=0;
    public int nodeSize(TreeNode root){
        if (root==null)return 0;
        size++;
        nodeSize(root.left);
        nodeSize(root.right);
        return size;
    }
    //子问题解决
    public int nodeSize2(TreeNode root){
        if (root==null)return 0;
        return nodeSize2(root.left)+
        nodeSize2(root.right)+1;
    }

    // 获取叶子节点的个数
    public int leafSize=0;
    public void getLeafSize(TreeNode root){
        if(root==null)return;
        if(root.left==null&&root.right==null) {
            leafSize++;
        }
        getLeafSize(root.left);
        getLeafSize(root.right);
    }
    //子问题思路：
    public int getLeafSize2(TreeNode root){
        if(root==null)return 0;
        if(root.left==null&&root.right==null) {
            return 1;
        }
        return getLeafSize2(root.left)+
        getLeafSize2(root.right);
    }

    // 获取第K层节点的个数
    public int getKLevelNodeCount(TreeNode root,int k){
        if(root==null)return 0;
        if(k==1){
            return 1;
        }
        return getKLevelNodeCount(root.left,k-1)+
                getKLevelNodeCount(root.right,k-1);
    }
    // 获取二叉树的高度
    public int getHeight(TreeNode root){
        if(root==null)return 0;
        int leftHeight=getHeight(root.left);
        int righeHeight=getHeight(root.right);
        return leftHeight>righeHeight?leftHeight+1:righeHeight+1;
    }

    // 检测值为value的元素是否存在
    public boolean find(TreeNode root, char key){
        if(root==null){
            return false;
        }
        //判断根节点是否相等
        if(root.val==key){
            return true;
        }
        boolean leftVal=find(root.left,key);
        if (leftVal==true){
            return true;
        }
        boolean rightVal=find(root.right,key);
        if (rightVal==true){
            return true;
        }
        return false;
    }
//判断两棵树是否相同
    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode() {}
     *     TreeNode(int val) { this.val = val; }
     *     TreeNode(int val, TreeNode left, TreeNode right) {
     *         this.val = val;
     *         this.left = left;
     *         this.right = right;
     *     }
     * }
     */
    class Solution {
        public boolean isSameTree(TreeNode p, TreeNode q) {
            //一个为空一个不为空
            if(p==null&&q!=null||p!=null&&q==null){
                return false;
            }
            //两个都为空
            if(p==null&&q==null){
                return true;
            }
            //走到这里这时两个都不为空了，判断值是否相等
            if(p.val!=q.val){
                return false;
            }
            return isSameTree(p.left ,q.left)&&
                    isSameTree(p.right ,q.right);

        }
    }
    //层序遍历
    public void levelOrder(TreeNode root){
        if(root==null){
            return;
        }
        //用队列完成
        Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            TreeNode cur=queue.poll();
            System.out.print(cur.val+" ");
            if(cur.left!=null){
                queue.offer(cur.left);
            }
            if(cur.right!=null){
                queue.offer(cur.right);
            }
        }
    }
    //2.返回List的每一层都是一个list
    public List<List<TreeNode>> levelOrder2(TreeNode root) {
        List<List<TreeNode>> ret = new ArrayList<>();
        if (root == null) {
            return ret;
        }
        //用队列完成
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            //求当前队列的大小
            int size = queue.size();
            //用tmp存出里面的list
            List<TreeNode> tmp = new ArrayList<>();
            //出队4次
            while (size != 0) {
                TreeNode cur = queue.poll();
                tmp.add(cur);
                size--;
                if (cur.left != null) {
                    queue.offer(cur.left);
                }
                if (cur.right != null) {
                    queue.offer(cur.right);
                }
            }
            ret.add(tmp);

        }
        return ret;
    }
    //判断一棵树是不是完全二叉树
    public boolean isCompleteTree(TreeNode root) {
        if (root == null) {
            return true;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            if (cur != null) {
                queue.offer(cur.left);
                queue.offer(cur.right);
            }else {
                //此时遇到了null
                break;
            }
        }
        //此时队列应该全为空
        while (!queue.isEmpty()){
            TreeNode cur=queue.poll();
            if(cur!=null){
                return false;
            }
        }
        return true;
    }

    //找公共节点
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            //判空
            if(root==null){
                return null;
            }
            //判断p,q是否在根节点
            if(root==q||root==p){
                return root;
            }
            //递归左右子树
            TreeNode leftTree=lowestCommonAncestor(root.left,p,q);
            TreeNode rightTree=lowestCommonAncestor(root.right,p,q);
            if(leftTree!=null&&rightTree!=null){
                return root;
            }else if(leftTree!=null){
                return leftTree;
            }else{
                return rightTree;
            }

        }
    //方法二：
    //找到root到node之间路径上的所有的节点存储到Stack中
    private boolean getPath(TreeNode root, TreeNode node, Stack<TreeNode> stack){
        if(root==null||node==null){
            return false;
        }
        //先入一个根节点
        stack.push(root);
        if(root==node){
            return true;
        }
        //递归左右子树，找目标节点
        boolean flg=getPath(root.left,node,stack);
        if(flg==true){
            return true;
        }
        boolean flg2=getPath(root.right,node,stack);
        if(flg2==true){
            return true;
        }
        stack.pop();
        return false;
    }
    //用栈求交点
    public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return null;
        }
        //实例化两个栈,
        Stack<TreeNode> stackP = new Stack<>();
        Stack<TreeNode> stackQ = new Stack<>();
        getPath(root, p, stackP);
        getPath(root, q, stackQ);
        //对栈进行操作，求p,q的大小
        int sizeP = stackP.size();
        int sizeQ = stackQ.size();
        //先走差值步
        if (sizeP > sizeQ) {
            int size = sizeP - sizeQ;
            while (size != 0) {
                stackP.pop();
                size--;
            }
        } else {
            int size = sizeQ - sizeP;
            while (size != 0) {
                stackQ.pop();
                size--;
            }
        }
        //两个同时走，如果相等，则随便返回一个相等的值，如果不相等，则出栈继续找
        while (!stackP.isEmpty() && !stackQ.isEmpty()) {
            if (stackP.peek().equals(stackQ.peek())) {
                return stackP.peek();
            }
            stackP.pop();
            stackQ.pop();
        }
        //都没有则返回空
        return null;
    }

    //根据一棵树的前序遍历和中序遍历构造一棵树
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return buildTreeChild(preorder,inorder,0,inorder.length-1);
    }
    public int priIndex;//成员变量，局部变量容易造成死循环
    private TreeNode buildTreeChild(int[] preorder,int[] inorder,int inbegin,int inend) {
        //没有左树或没有右数了（inbegin>inend)
        if(inbegin>inend){
            return null;
        }
        //创建根节点
        TreeNode root =new TreeNode((char) preorder[priIndex]);
        //找到前序遍历在中序遍历中对应的根节点的下标
        int rootIndex=findIndex(inorder,inbegin,inend,preorder[priIndex]);
        if(rootIndex==-1){
            return null;
        }
        priIndex++;
        //创建左子树和右子树
        root.left=buildTreeChild(preorder,inorder,inbegin,rootIndex-1);
        root.right=buildTreeChild(preorder,inorder,rootIndex+1,inend);
        return root;
    }
    //找中序遍历中根节点所在的位置
    private int findIndex(int[] inorder,int inbegin,int inend,int key){
        //循环遍历，相等则返回下标
        for (int i=inbegin;i<=inend;i++){
            if(inorder[i]==key){
                return i;
            }
        }
            return -1;
    }
    //非递归方式打印前序遍历
    public void preorderTraversal(TreeNode root) {
        if(root==null){
            return;
        }
        Stack<TreeNode> stack=new Stack<>();
        TreeNode cur=root;
        TreeNode top=null;
        while (cur!=null||!stack.isEmpty()){
            while (cur!=null){
                stack.push(cur);
                System.out.print(cur.val+" ");
                cur=cur.left;
            }
            top=stack.pop();
            cur=top.right;
        }
    }
    //非递归方式打印中序遍历
    public void inorderTraversal(TreeNode root) {
        if(root==null){
            return;
        }
        Stack<TreeNode> stack=new Stack<>();
        TreeNode cur=root;
        TreeNode top=null;
        while (cur!=null||!stack.isEmpty()){
            while (cur!=null){
                stack.push(cur);
                cur=cur.left;
            }
            top=stack.pop();
            System.out.print(top.val+" ");
            cur=top.right;
        }
    }

    //非递归方式打印后序遍历
    public void postorderTraversal(TreeNode root) {
        if(root==null){
            return;
        }
        Stack<TreeNode> stack=new Stack<>();
        TreeNode cur=root;
        TreeNode top=null;
        TreeNode prev=null;
        while (cur!=null||!stack.isEmpty()){
            while (cur!=null){
                stack.push(cur);
                cur=cur.left;
            }
            top=stack.peek();
            if(top.right==null||top.right==prev){
                top=stack.pop();
                System.out.print(top.val+" ");
                prev=top;//当前这个节点被打印了。
            }else{
                cur=top.right;
            }

        }
    }
    }